// Implementation file for Queue ADT; class specification in file Queue2.h.
// Class is templated.
// Uses linked list of items with a pointer to the head and one to the tail.

#include <cstddef>		 	// For NULL
using namespace std;

template <class ItemType>
struct NodeType
{
    ItemType info;
    NodeType* next;
};

template <class ItemType>
QueType<ItemType>::QueType()		// Class constructor.
// Post:  qFront and qRear are set to NULL.
{
    qFront = NULL;
    qRear = NULL;
}


template <class ItemType>		// Class destructor.
QueType<ItemType>::~QueType()
{
    NodeType<ItemType>* tempPtr;

    while (qFront != NULL)
    {
        tempPtr = qFront;
        qFront = qFront->next;
        delete tempPtr;
    }
}


template <class ItemType>
QueType<ItemType>::QueType(const QueType<ItemType>& source)
//copy constructor
{
	qFront = NULL;
	qRear = NULL;
	
	if (source.qFront == NULL)
		return;

	NodeType<ItemType>* sourcePtr;
	sourcePtr = source.qFront;

	//copy first node
	qFront = new NodeType<ItemType>;
	if (qFront == NULL)
	{
		cout << "Insufficient memory.\n";
		exit(1);
	}
	qFront->info = sourcePtr->info;
	sourcePtr = sourcePtr->next;
	qRear = qFront;

	//copy rest of nodes
	while (sourcePtr != NULL)
	{
		qRear->next = new NodeType<ItemType>;
		if (qRear == NULL)
		{
			cout << "Insufficient memory.\n";
			exit(1);
		}
		qRear = qRear->next;
		qRear->info = sourcePtr->info;
		sourcePtr = sourcePtr->next;
	}
	qRear->next = NULL;
}


template <class ItemType>
QueType<ItemType> QueType<ItemType>::operator =(const QueType<ItemType>& source)
//assignment operator
{
	//check x = x case
	if (this == &source)
		return *this;
	
	//delete existing nodes
	NodeType<ItemType>* tempPtr;
    while (qFront != NULL)
    {
        tempPtr = qFront;
        qFront = qFront->next;
        delete tempPtr;
    }
    qRear = NULL;

	//copy from source	
	if (source.qFront == NULL)
		return *this;

	NodeType<ItemType>* sourcePtr;
	sourcePtr = source.qFront;

	//copy first node
	qFront = new NodeType<ItemType>;
	if (qFront == NULL)
	{
		cout << "Insufficient memory.\n";
		exit(1);
	}
	qFront->info = sourcePtr->info;
	sourcePtr = sourcePtr->next;
	qRear = qFront;

	//copy rest of nodes
	while (sourcePtr != NULL)
	{
		qRear->next = new NodeType<ItemType>;
		if (qRear == NULL)
		{
			cout << "Insufficient memory.\n";
			exit(1);
		}
		qRear = qRear->next;
		qRear->info = sourcePtr->info;
		sourcePtr = sourcePtr->next;
	}
	qRear->next = NULL;
	return *this;
}


template <class ItemType>
void QueType<ItemType>::MakeEmpty()
// Post: Queue is empty; all elements have been deallocated.
{
    NodeType<ItemType>* tempPtr;

    while (qFront != NULL)
    {
        tempPtr = qFront;
        qFront = qFront->next;
        delete tempPtr;
    }
    qRear = NULL;
}


template <class ItemType>
bool QueType<ItemType>::IsFull() const
// Returns true if there is no room for another ItemType on the free store;
// false otherwise.
{
    NodeType<ItemType>* ptr;
    ptr = new NodeType<ItemType>;
    if (ptr == NULL)
        return true;
    else
    {
        delete ptr;
        return false;
    }
}


template <class ItemType>
bool QueType<ItemType>::IsEmpty() const
// Returns true if there are no elements on the queue; false otherwise.
{
    return (qFront == NULL);
}


template <class ItemType>
bool QueType<ItemType>::Enqueue(ItemType newItem)
// Adds newItem to the rear of the queue.
// Pre:  Queue has been initialized
// Post: returns false if queue is full, 
//		 else newItem is at rear of queue and returns true

{
    NodeType<ItemType>* newNode;

    newNode = new NodeType<ItemType>;

    if (newNode == NULL)
		return false;

	newNode->info = newItem;
    newNode->next = NULL;
    if (qFront == NULL)
        qFront = newNode;
    else
        qRear->next = newNode;
    qRear = newNode;

	return true;
}


template <class ItemType>
bool QueType<ItemType>::Dequeue(ItemType& item)
// Removes front item from the queue and returns it in item.
// Pre:  Queue has been initialized
// Post: returns false if queue is empty
//		 else, front element has been removed from queue,
//       item is a copy of removed element, and returns true
{
	if (qFront == NULL)
		return false;

	item = qFront->info;

    NodeType<ItemType>* tempPtr;
    tempPtr = qFront;
    qFront = qFront->next;
	delete tempPtr;

    if (qFront == NULL)
        qRear = NULL;

	return true;
}
